package leetcode.pre50;


import leetcode.pre100.Code81_FindTargetInRotateArray2;

/**
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * <p>
 * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
 * <p>
 * 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 * <p>
 * 你可以假设数组中不存在重复的元素。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [4,5,6,7,0,1,2], target = 0
 * 输出: 4
 * 示例 2:
 * <p>
 * 输入: nums = [4,5,6,7,0,1,2], target = 3
 * 输出: -1
 * <p>
 * <p>
 * 拓展1：考虑有可能相同元素，见
 * {@link Code81_FindTargetInRotateArray2}
 * <p>
 * 旋转数组其他问题
 * {@link leetcode.a_总结分布.Code13_旋转数组问题}
 *
 * @since 2019/11/24 0024 上午 10:27
 */
public class Code33_FindTargetInRotateArray {
    public static void main(String[] args) {
        int[] nums = {9,10,11,12,13,14,15,6,7,8};
        System.out.println(search(nums, 7));
    }

    /**
     * 方式2:
     * 题目要求 O(logN)的时间复杂度，基本可以断定本题是需要使用二分查找，怎么分是关键。
     * <p>
     * 由于题目说数字了无重复，举个例子：
     * <p>
     * 1 2 3 4 5 6 7 可以大致分为两类，
     * <p>
     * 第一类 2 3 4 5 6 7 1 这种，也就是 nums[start] <= nums[mid]。此例子中就是 2 <= 5。
     * <p>
     * 这种情况下，前半部分有序。因此如果 nums[start] <=target<nums[mid]，
     * <p>
     * 则在前半部分找，否则去后半部分找。
     * <p>
     * 第二类 6 7 1 2 3 4 5 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2。
     * <p>
     * 这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]，
     * <p>
     * 则在后半部分找，否则去前半部分找。
     * <p>
     */
    public static int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid;
        //TODO 注意这里要写 = ，否则[3,1] target = 1 找不到
        while (left <= right) {
            mid = (left + right) >> 1;
            if (nums[mid] == target) {
                return mid;
            }
            //前半部分肯定有序
            if (nums[left] <= nums[mid]) {
                //target在前部分，继续搜索
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    //否则target < nums[left] 或者target > nums[mid]，要向后半部分搜索
                    left = mid + 1;
                }
                //nums[left] > nums[mid],在右半部分，肯定有序
            } else {
                //继续往后搜
                if ( target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    //往前搜,target < nums[mid] 或者 target > nums[right]
                    assert target < nums[mid] || target > nums[right];
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
    /**
     * 方式1：直接找，O(n)
     */
}
